package com.fm.text.searcher;

import com.fm.base.struct.BasicHashMap;
import com.fm.base.struct.BasicHashSet;
import com.fm.base.util.Pair;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 基于AC算法
 */
public class WordSearcher {

	public static Builder builder() {
		return new Builder();
	}

	private State root = new State();

	private WordSearcher() {
	}

	private State nextState(State current, Character character) {
		State nextState = current.links == null ? null : current.links.get(character);
		if (current == root && nextState == null) {
			return root;
		}
		return nextState;
	}

	public List<Word> find(CharSequence text) {
		List<Word> results = new LinkedList<>();
		State current = this.root;
		for (int position = 0; position < text.length(); position++) {
			Character character = text.charAt(position);

			State newCurrent = nextState(current, character);
			while (newCurrent == null) {
				current = current.failure;
				newCurrent = nextState(current, character);
			}
			current = newCurrent;

			while (true) {
				if (newCurrent.word != null) {
					results.add(new Word(position - newCurrent.word.length(), position, newCurrent.word, newCurrent.data));
				}
				if (newCurrent == root) {
					break;
				} else {
					newCurrent = newCurrent.failure;
				}
			}
		}
		return results;
	}

	public void addWordInc(String word) {
		addWordInc(word, null);
	}

	public void addWordInc(String word, Object data) {
		State currentState = this.root;
		int pos = 0;
		int len = word.length();
		State temp;
		for (; pos < len; pos++) {
			Character c = word.charAt(pos);
			if (currentState.links == null) {
				break;
			} else {
				temp = currentState.links.get(c);
				if (temp == null) {
					break;
				} else {
					currentState = temp;
				}
			}
		}

		if(pos == len) {// existing path, just set value
			currentState.word = word;
			currentState.data = data;
		} else {
			temp = currentState;
			for(; pos < len; ++ pos) {
				if (temp.links == null) {
					temp.links = new BasicHashMap<>(1, 1F, 0.2F);
				}
				State newState = new State();
				temp.links.put(word.charAt(pos), newState);
				temp = newState;
			}
			temp.word = word;
			temp.data = data;

			if(currentState == this.root) {
				build();
			} else {
				Queue<State> queue = new LinkedList<>();
				queue.add(currentState);
				if (currentState.beFailureTo != null) {
					queue.addAll(currentState.beFailureTo);
				}
				build(queue);
			}
		}
	}

	private void build(Queue<State> queue) {
		while (!queue.isEmpty()) {
			State current = queue.poll();
			if (current.links != null) {
				for (Pair<Character, State> pair : current.links) {
					queue.add(pair.right);

					// 失败指正开始逐级向上遍历查看是否匹配，直至root遍历完为止
					State failureTrace = current.failure;
					while (true) {
						State nextState = failureTrace.links == null ? null : failureTrace.links.get(pair.left);
						if (nextState == null) {
							failureTrace = failureTrace.failure;
							if (failureTrace == null) { // 只有root的失败指针才是null
								pair.right.failure = root;// root不需要知道谁的失败指针指向他
								break;
							}
						} else {
							pair.right.failure = nextState;
							if (nextState.beFailureTo == null) {
								nextState.beFailureTo = new BasicHashSet<>();
							}
							nextState.beFailureTo.append(pair.right);
							break;
						}
					}
				}
			}
		}
	}

	private void build() {
		Queue<State> queue = new LinkedList<>();

		//children of root
		for (Pair<Character, State> pair : root.links) {
			State child = pair.getRight();
			child.failure = root;
			queue.add(child);
		}

		build(queue);
	}

	public static class Builder {
		private WordSearcher trie;

		private Builder() {
			trie = new WordSearcher();
		}

		public WordSearcher build() {
			trie.build();
			return trie;
		}

		public void addWord(String word) {
			addWord(word, null);
		}

		public void addWord(String word, Object data) {
			if (word.length() > 0) {
				State cur = trie.root;
				int len = word.length();
				for (int i = 0; i < len; i++) {
					if (cur.links == null) {
						cur.links = new BasicHashMap<>(1, 1F, 0.2F);
					}
					State next = cur.links.get(word.charAt(i));
					if (next == null) {
						next = new State();
						cur.links.put(word.charAt(i), next);
					}
					cur = next;
				}
				cur.word = word;
				cur.data = data;
			}
		}
	}
}
